package basic.study.algorithms.sort;

import java.util.ArrayList;
import java.util.Arrays;

/*
 * 冒泡排序、插入排序、选择排序
 */
public class BasicSorts {

    public static void main(String[] args) {
        int[] a = new int[]{14,25,78,34,46,92,76};
        //insertSort(a,a.length);
        shellSort(a);
        System.out.println(Arrays.toString(a));
    }


    //冒泡排序,a是数组，n表示数组大小
    public static void bubbleSort(int[] a, int n) {
        if(n <= 1) return;

        for(int i=0; i < n; i++) {
            //提前退出标志位
            boolean flag = false;
            for(int j = 0; j< n-i-1; j++) {
                if(a[j] > a[j+1]) {
                    int temp = a[j];
                    a[j] = a[j+1];
                    a[j+1] = temp;
                    flag = true;
                }
            }
            if(!flag) break;  // 没有数据交换，提前退出
        }

    }

    public static void insertSort(int[] a, int n) {
        if(n <= 1) return;

        for (int i=1; i<n; i++) {
            int value = a[i];
            int j = i-1;
            for(; j >= 0; j--) {
                if(a[j] > value) {
                    a[j+1] = a[j];
                } else {
                    break;
                }
            }
            a[j+1] = value;
        }
    }

    public static void selectionSort(int[] a, int n) {
        if (n <= 1) return ;

        for (int i = 0; i < n-1; i++) {
            int minIndex = i;
            for(int j = i + 1; j < n; j++) {
                if(a[j] < a[minIndex]) {
                    minIndex = j;
                }
            }

            int temp = a[minIndex];
            a[minIndex] = a[i];
            a[i] = temp;
        }
    }

    public static void shellSort(int[] arr) {
        int len = arr.length;
        if(len == 1) return;

        int step = len / 2;
        while (step >= 1) {
            //对各个分组进行排序，这里不是一组排序完后才换下一组，是轮流排序
            for(int i = step; i < len; i++) {
                int value = arr[i];
                int j = i - step;
                for(; j >= 0; j--) {
                    if(arr[j] >value) {
                        arr[j+step] = arr[j];
                    }else {
                        break;
                    }
                }
                arr[j+step] = value;
            }
            step /= 2;
        }
    }
}
